package middle;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import middle.Solution_71.Status;

public class Solution_99 {
    public void recoverTree(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        TreeNode node = root.left;
        while (!stack.empty() || node != null) {
            if (node != null) {
                stack.add(node);
                node = node.left;
            } else {
                TreeNode pop = stack.pop();
                list.add(pop);
                node = pop.right;
            }
        }
        TreeNode one = null, two = null;
        for (int i = 0; i < list.size(); i++) {
            long pre = i == 0 ? Long.MIN_VALUE : list.get(i-1).val;
            long next = i == list.size() - 1 ? Long.MIN_VALUE : list.get(i+1).val;
            if (pre >= list.get(i).val || list.get(i).val >= next) {
                one = list.get(i);
                break;
            }
        }
        for (int i = list.size() - 1; i >= 0; i--) {
            long pre = i == 0 ? Long.MIN_VALUE : list.get(i-1).val;
            long next = i == list.size() - 1 ? Long.MAX_VALUE : list.get(i+1).val;
            if (pre >= list.get(i).val || list.get(i).val >= next) {
                two = list.get(i);
                break;
            }
        }
        int temp = one.val;
        one.val = two.val;
        two.val = temp;
    }

    public static void main(String[] args) {
        Solution_99 model = new Solution_99();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.right = new TreeNode(4);
        root.right.left = new TreeNode(2);
        model.recoverTree(root);
        System.out.println();
    }

    static class TreeNode {

        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
